

package main.new_2024.month_03;


import main.dataStruct.TreeNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @Description: todo 1261. 在受污染的二叉树中查找元素
 * 给出一个满足下述规则的二叉树：
 * root.val == 0
 * 如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
 * 如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2
 * 现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。
 * 请你先还原二叉树，然后实现 FindElements 类：
 * FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
 * bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2024/2/27
 * @Param:
 * @return:
 **/
public class Solution0312 {

    //在受污染的二叉树中查找元素
    class FindElements {

        private final Set<Integer> s = new HashSet<>();

        public FindElements(TreeNode root) {
            dfs(root,0);
        }

        public boolean find(int target) {
            return s.contains(target);
        }
        private void dfs(TreeNode node, int val) {
            if (node == null) {
                return;
            }
            s.add(val);
            dfs(node.left, val * 2 + 1);
            dfs(node.right, val * 2 + 2);
        }

    }
}

